package com.hdu.other.monotonyStack;

public class lc316 {
    class Solution {
        public String removeDuplicateLetters(String s) {
            int[] letterCount = new int[26];
            for (int i = 0; i < s.length(); i++) {
                letterCount[s.charAt(i) - 'a']++;
            }
            boolean[] inStack = new boolean[26];
            int len = s.length();
            char[] stack = new char[len];
            int r = 0;
            for (int i = 0; i < len; i++) {
                char curChar = s.charAt(i);
                if (!inStack[curChar - 'a']) {
                    while (r > 0 && curChar < stack[r - 1] && letterCount[stack[r - 1] - 'a'] > 0) {
                        inStack[stack[r - 1] - 'a'] = false;
                        r--;
                    }
                    stack[r++] = curChar;
                    inStack[curChar - 'a'] = true;
                }
                letterCount[curChar - 'a']--;
            }
            return new String(stack, 0, r);
        }
    }
}
